#include <iostream>
#include <cstdlib>
using namespace std;

/*
思路:动态规划

从n个数a[0~n-1]中选取k个数b[0~k-1]，求他们乘积的最大值，等效于
从n个数中选取k个数，其中k个数的最后一个数b[k-1]为a[i],i为0~n-1,此时
可以构成长度为i的数组arr[0~i-1],其中arr[i]表示选取的k个数的最后一个数为a[i]时
选取的数的乘积的最大值。
然后找到arr[0~i-1]中的最大值，就是题目所需的结果。

例如：
从数组
0 1 2 3 4 5 6 7 8 9 10 （索引）
3 4 1 1 1 1 1 2 3 2 2 中选取4个数，并且相邻两个数的距离小于4
则可以按照如下的思路解答
选取的最后一个数的索引为[0] 不可能，因为前面没有其他数了，不能选出3个出来
选取的最后一个数的索引为[1] 不可能，因为前面只有一个数，不能选出3个出来
选取的最后一个数的索引为[2] 不可能
选取的最后一个数的索引为[3] 则还需要在前面[0~2]中选取三个数，保证最后的乘积最大，得到arr[3]
。。。
。。。
选取的最后一个数的索引为[10] 则还需要在前面[0~9]中选出其他三个数，保证最后的乘积最大，得到arr[10]。
上面将我们的问题分解成了11个子问题，最终求出来了11个值，其中最大的那个就是我们所需要的那个。
即arr[0~10]中最大的值。（无意义的值忽略，实际操作时可以将他们设置为负无穷）

上面虽然把问题细化成了多个子问题，但是每个子问题也并不好求解，例如对问题
“选取的最后一个数的索引为10，则还需要在前面0-9的索引中选出其他三个，保证最后的乘积最大。”
如何选取另外三个数？？？

答案是动态规划。
1. 首先从n个数中选取一个数，满足题目的要求，找到一个数的乘积（他们本身）。即得到数组
3 4 1 1 1 1 1 2 3 2 2
拓展：他们中的最大值为4，因此从这11个数中选取一个数，使他们的乘积最大，得到的最大值为4
2. 根据第一步的结果，找到两个数的乘积。保证第二个数与第一个数的最大距离为4。得到数组
* 12 4 4 4 4 1 2 6 6 6
第一个*表示不合法，如果第二个数的索引为[0]，第一个数的索引必须小于[0]，矛盾
第二个数12表示当前索引值为[1]的数选取后，从前面最远相邻4个数中找到一个求乘运算后得到最大值的数
。。。
最后一个6表示，选取索引值为[10]的数，从前面最远相邻4个数中选取一个求乘运算后得到最大数的数，
我们循环找到索引值为[8]的3，求得的值为6
拓展：该数组的最大值为12，因此如果从数组中选取两个数，使他们的乘积最大，则结果是12
3. 根据第二步的结果，找到三个数的乘积。保证第三个数与第二步中选取的数的最大距离为4。得到数组
* * 12 12 12 12 4 8 12 12 12
举个例子，上面数组中8是如何得到的。
8的索引值为[7]，指向的原始数组的值为2。为了找到选取3个数使得乘积最大，且最后一个数为第[7]个数
我们计算以第[7]个数为选取的第三个数，求得的最大值是第[7]个数*上一次选择第[5]个数或者di[4]个数
或者第[3]个数，得到的值为8

备注：
* 12 4 4 4 4 1 2 6 6 6  上一步的数组
3 4  1 1 1 1 1 2 3 2 2  初始数组
保证初始数组和上一步的数组选取的值的最大距离为4，找到最大值

4. 根据第三步的结果，同样的步骤计算出第四个数组。
* * * 12 12 12 12 24 36 24 24
该数组的最大值为36,因此最总的结果为36

需要注意的是，原始数组中可能存在负数，因此需要保存每次的最大正数和最小负数
我们定义二维数组保存中间结果。
代码如下
*/

// 11 3 4 1 1 1 1 1 2 3 2 2 4 4

inline long long max(long long a, long long b) { return (a>b ? a : b); }
inline long long min(long long a, long long b) { return (a>b ? b : a); }

int main(int argc, char* argv[])
{
	// 获取输入
	long long N, K, D, stu[51],zheng[11][51], fu[11][51], result;
	cin >> N;
	for (int j = 1; j <= N; j++)
		cin >> stu[j];
	cin >> K >> D;
	for (int i = 1; i <=K; i++)
		for (int j = 1; j <= N; j++)
		{
			zheng[i][j] = fu[i][j] = 0;
		}
	for (int j = 1; j <= N; j++)
		zheng[1][j] = fu[1][j] = stu[j];

	for (int i = 0; i <= K; i++)
	{
		for (int j = 0; j <= N; j++)
			cout << zheng[i][j] << "\t";
		cout << endl << endl;
	}

	system("pause");

	result = 0X8000000000000000ll;

	for (int i = 2; i <= K; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			for (int k = 1; k <= D && j-k>=1; k++)
			{
				zheng[i][j] = max(zheng[i][j], max(zheng[i - 1][j - k] * stu[j], fu[i - 1][j - k] * stu[j]));
				fu[i][j] = min(fu[i][j], min(zheng[i - 1][j - k] * stu[j], fu[i - 1][j - k] * stu[j]));
			}
		}
	}
	for (int j = 1; j <= N; j++)
		result = max(result, zheng[K][j]);
	cout << result << endl;

	for (int i = 0; i <= K; i++)
	{
		for (int j = 0; j <= N; j++)
			cout << zheng[i][j] << "\t";
		cout << endl;
	}
	system("pause");
	return 0;
}

